Theo ghi chép trong các sách: Tam quốc chí, Ngụy Thư và Lữ Bố truyện, cha ông là Lữ Lương đã theo nghiệp tổ phụ, trấn thủ vùng biên giới. Mẹ là người họ Hoàng, là con một đại phú hào, thông minh, hiền lành, có tri thức, hiểu lễ nghĩa. Ngay từ nhỏ, Lữ Bố đã thể hiện là một đứa trẻ có sức mạnh phi thường, tinh thông võ nghệ, rất hiếu thắng, luôn giành chiến thắng trong những "trận đấu" với bạn bè đồng trang lứa. Hệ quả, không ai dám chơi đùa với Lữ Bố.

Lớn lên, Lữ Bố được gia đình cho học cầm kì thi thư và luyện võ. Nhưng sở thích lớn nhất của ông vẫn là côn quyền, cung tên, đao kiếm và luôn muốn cho mọi người thấy mình dũng mãnh đến nhường nào. Sử sách Trung Quốc ghi lại rằng năm 11 tuổi Lữ Bố đã đánh bại đại lực sĩ nổi tiếng trong dòng tộc. Sau sự kiện đó, cả quận Ngũ Nguyên đều biết đến cái tên thiếu niên anh hùng Lữ Bố.